package com.hhc.t;

import java.util.HashMap;

/**
 * 推理二叉树
 */
public class T3 {
    int[] preorder;
    HashMap<Integer,Integer> hashMap = new HashMap<>();

    public TreeNode tTree(int[] preorder, int[] inorder){
        this.preorder = preorder;
        for(int i = 0;i < inorder.length; i++)
            hashMap.put(inorder[i], i);
        return a(0,0,inorder.length - 1);
    }

    TreeNode a(int root, int left, int right){
        if(left > right)  return null;  // 递归终止
        TreeNode node = new TreeNode(preorder[root]);  // 建立根节点
        int i = hashMap.get(preorder[root]); // 划分根节点、左子树、右子树
        node.left = a(root + 1 , left, i - 1); // 开启左子树递归
        node.right = a(root + i - left + 1, i + 1, right); // 开启右子树递归
        return node;  // 回溯返回根节点

    }

}
